package cn.walls1717.leetcode.array;

import java.util.Stack;

/**
 * 844. 比较含退格的字符串
 * 力扣地址：https://leetcode-cn.com/problems/backspace-string-compare/
 *
 * @author walls1717
 * @since 2022-05-01
 **/
public class T844 {

    public static void main(String[] args) {
        System.out.println(backspaceCompare("ab##", "c#d#"));
    }

    /**
     * 双指针法
     *
     * 设置两个指针，分别指向字符串 s 和 t 的末尾
     * 再设置两个变量用来记录字符串中 '#' 的个数
     * 进入大循环之后，第一个 while 循环，判断指针指向的元素是否为 '#'
     * 如果不是 '#' 且当前字符串中的 '#' 个数为 0 时，跳出循环
     * 进入下一个 while 循环，这个 while 循环遍历第二个数组，与第一个 while 循环操作一样
     * 找到了一个没有被退格符删除的元素，然后对这个元素进行比较，如果不相等，直接就返回 false
     * 如果相等，那么将指针前移，再次判断
     *
     * @param s 字符串
     * @param t 字符串
     * @return 是否相等
     */
    public static boolean backspaceCompare(String s, String t) {
        // 设置 i 和 j 用来从后往前遍历字符串
        // 可以使用charAt()按索引读取字符串元素
        int i = s.length() - 1;
        int j = t.length() - 1;
        // 用来存储字符串中 '#' 的个数
        // 如果遇到 '#' 则 +1，遇到不是 '#' 的 -1
        // 直到 skipS 或 skipT 的值为 0 了结束本次循环
        int skipS = 0;
        int skipT = 0;

        /*
        第一层 while 之所以用 || ，是因为可能一个字符串遍历完毕了，
        但是另一个字符串还没有遍历完毕，所以仍然需要进入循环
        在循环里面有嵌套 while 进行判断那个字符串还没有遍历完毕再进行遍历
        */
        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    ++skipS;
                    --i;
                } else if (skipS > 0) {
                    --skipS;
                    --i;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    ++skipT;
                    --j;
                } else if (skipT > 0) {
                    --skipT;
                    --j;
                } else {
                    break;
                }
            }
            /*
            这里又使用 && 判断是因为有可能一个数组遍历完毕了，另一个数组还没有遍历完毕
            所以必须判断 i和j 都没有越界，再判断两个值是否相等

            如果有一个数组已经遍历完毕，另一个数组仍然没有遍历完毕，那么说明这两个数组
            不相等，直接返回 false 即可
             */
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false;
                }
            } else if (i >= 0 || j >= 0) {
                return false;
            }
            --i;
            --j;
        }
        return true;
    }

    /**
     * 用栈解决
     * 利用栈先进后出的特性
     * 逐个字符判断，如果这个字符不是 '#' 则放入栈中
     * 如果是 '#' 则判断栈是否为空，如果是空，则弹出栈中元素
     * 最后判断两个字符串栈中的元素是否相等
     *
     * @param s 字符串
     * @param t 字符串
     * @return 是否相等
     */
    public static boolean backspaceCompare2(String s, String t) {
        // 用来存放字符串 s
        Stack<Character> stackS = new Stack<>();
        // 用来存放字符串 t
        Stack<Character> stackT = new Stack<>();
        // 将字符串s和t转化为字符数组
        char[] charsS = s.toCharArray();
        char[] charsT = t.toCharArray();
        for (char charS : charsS) {
            // 遍历 s 字符数组，如果元素不为 '#'，将元素放入栈中
            if (charS != '#') {
                stackS.push(charS);
            } else {
                // 如果元素为 '#' 先判断栈是否为空，如果为空则不用弹出
                // 如果不为空，则弹出栈中元素
                if (!stackS.isEmpty()) {
                    stackS.pop();
                }
            }
        }

        // 与操作 s 字符数组相同对 t 字符数组进行操作
        for (char charT : charsT) {
            if (charT != '#') {
                stackT.push(charT);
            } else {
                if (!stackT.isEmpty()) {
                    stackT.pop();
                }
            }
        }
        // 判断栈中元素是否相同
        return stackS.equals(stackT);
    }
}
